package zw_401_500.zw_476_数字的补数;

class Solution {

    public static void main(String[] args) {
        int num = 5;
        int n = findComplement(num);
        System.out.println(n);
    }

    /**
     * 方法一：位运算
     * 时间复杂度：O(lognum)。找出num 二进制表示最高位的 1 需要的时间为O(lognum)。
     * 空间复杂度：O(1)。
     *
     * @param num
     * @return
     */
    public static int findComplement(int num) {
        int highbit = 0;
        for (int i = 1; i <= 30; ++i) {
            if (num >= 1 << i) {
                highbit = i;
            } else {
                break;
            }
        }
        int mask = highbit == 30 ? 0x7fffffff : (1 << (highbit + 1)) - 1;
        return num ^ mask;
    }


//    public static int findComplement(int num) {
//        long ans = 1;
//        while (ans <= num) {
//            ans *= 2;
//        }
//        return (int) ans - 1 - num;
//    }
}
